package lc.q101_150;

/**
 * 排序链表
 */
public class Q148 {

    public ListNode sortList(ListNode head) {
        // 中间指针断开，然后合起来
        ListNode res = new ListNode();
        res.next = head;
        int totalSize = 0;
        while (head != null) {
            totalSize ++;
            head = head.next;
        }
        int perSize = 1;
        while (perSize < totalSize) {
            merge(res, perSize, totalSize);
            perSize *= 2;
        }
        return res.next;
    }

    private void merge(ListNode res, int perSize, int totalSize) {
        ListNode prev = res;
        ListNode tail = res;
        int times = 1;
        while (prev != null && prev.next != null && 2 * times * perSize + perSize < totalSize) {
            ListNode left = prev.next;
            ListNode right = prev.next;
            ListNode leftTail = prev;
            int i = 0;
            for ( ;i < perSize && right.next != null; i++) {
                right = right.next;
                leftTail = leftTail.next;
            }
            if (i < perSize) {
                break;
            }
            leftTail.next = null;
            int lp = 0,rp=0;
            System.out.println("left:"+left);
            System.out.println("right:"+right);
            while ( lp < perSize && rp < perSize && right != null && left != null) {
                if (left.val < right.val) {
                    lp ++;
                    left = left.next;
                } else {
                    ListNode node = right.next;
                    right.next = left;
                    prev.next = right;
                    right = node;
                    rp ++;
                }
                prev = prev.next;
            }
            leftTail.next = right;
            // 下一轮从哪里开始？
            for (int j = 0; j < 2 * perSize && tail != null; j++) {
                tail = tail.next;
            }
            prev = tail;
            times ++;
        }

    }





    public static void main(String[] args) {
        ListNode head = ListNode.buildByArr(new int[]{-1,3,1,2,0,9,5,8,10});
        ListNode listNode = new Q148().sortList(head);
        System.out.println(listNode);
    }

}
